/*https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
902.最大为N的数字组合
medium, 方钊堉 2024.10.07
数位DP*/

class Solution {
public:
    vector<int> num; // 存储数字n的每一位数字
    int s; // 数字n的位数
    int dp[11]; // 记忆化数组，用于存储已经计算过的状态避免重复计算
    vector<int> tr; // 存储允许使用的数字
    
    // 深度优先搜索函数，用于递归计算满足条件的数字个数
    int dfs(int oo, bool ld, bool lt) {
        if(oo >= s) return !ld; // 如果已经处理完所有位数，则检查是否为前导零
        if(!ld && !lt && dp[oo] >= 0) return dp[oo]; // 如果不是前导零且不是紧贴限制，使用记忆化结果
        int up = (lt) ? num[oo] : 9; // 当前位的最大值，如果是紧贴限制则为num[oo]，否则为9
        int res = 0;
        // 遍历允许使用的数字集合
        for(int i = 0 + !ld; i < tr.size(); ++i) { // 跳过前导零的情况
            if(tr[i] > up) break; // 如果当前数字大于最大值，跳出循环
            // 递归调用，更新位置、是否为前导零、是否紧贴限制
            res += dfs(oo + 1, ld && (!tr[i]), lt && (tr[i] == up));
        }
        if(!ld && !lt) dp[oo] = res; // 如果不是前导零且不是紧贴限制，保存结果到dp数组中
        return res;
    }

    // 主函数，计算不超过给定数字n的、只包含digits中数字的正整数个数
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        // 将数字n拆分成各位数字并存储在num中
        while(n) {
            num.push_back(n % 10);
            n /= 10;
        }
        reverse(num.begin(), num.end()); // 反转num，使其从高位到低位排列
        // 初始化允许使用的数字集合
        tr.push_back(0); // 允许前导零的存在
        for(string& s: digits) {
            tr.push_back(stoi(s)); // 将字符串转换为整数后加入tr
        }
        s = num.size(); // 获取数字n的位数
        memset(dp, -1, sizeof(dp)); // 初始化dp数组，-1表示未计算过
        return dfs(0, true, true); // 开始深度优先搜索，初始状态为第一位、是前导零、紧贴限制
    }
};